/*!
\file AlgDijkstra.cpp
\brief Contains implementation of AlgDijkstra.
\ingroup Plugins
*/

#include"AlgDijkstra.h" 

#define INF 99999.0

/*!
\def INF
\brief A very big number.
*/

AlgDijkstra::AlgDijkstra( Graph *g ): Algorithm( g ){
	containerAdd();
}

AlgDijkstra::~AlgDijkstra(){
	
}

void AlgDijkstra::run(){
	Node *source = getNode("Please select the source Node");
	for( unsigned int i = 0; i < graph()->numNodes(); i++ ){
		const Node &n = graph()->node(i);
		bool isSource = n == *source;
		c().push_back( (new ContainerElement)->setNode(n)->setData(isSource?0.0:INF)->setData(isSource?1:0) );
	}
	
	QList<Edge> edgesFromSource = graph()->edgesFrom(*source);
	for( int i = 0; i < edgesFromSource.size(); i++ ){
		const Edge &e = edgesFromSource[i];
		const Node &n = otherNode(e, *source);
		double cost = e.label().toDouble();
		if( cost < distance( n ) )
			setDistance( n, cost, e );
		
	}
	
	for( unsigned int i = 1; i < graph()->numNodes(); i++ ){
		const Node *nodeW = minUnseenNode();
		if(nodeW==0)
			return;
		
		for( unsigned int j = 0; j < c().size(); j++ ){
			if( c()[j]->dataInt() == 1 )
				continue;
			const Node *nodeV = c()[j]->node();
			
			int edgeID = (*graph())[nodeW->identifier()][nodeV->identifier()];
			if( edgeID < 0 )
				continue;
			
			const Edge &edge = graph()->edgeWithId(edgeID);
			
			double cost = distance(*nodeW) + edge.label().toDouble();
			if( cost < distance(*nodeV) )
				setDistance(*nodeV, cost, edge);
		}
	}
}

const Node *AlgDijkstra::minUnseenNode(){
	double minCost = INF;
	int minI = -1;
	for( unsigned int i = 0; i < c().size(); i++ ){
		if( c()[i]->dataInt() == 0 ){
			if( c()[i]->dataDouble() < minCost ){
				minCost = c()[i]->dataDouble();
				minI = i;
			}
		}
	}
	if( minI == -1 )
		return 0;
	
	c()[minI]->setData(1);
	return c()[minI]->node();
}

double AlgDijkstra::distance( const Node &n ){
	for( unsigned int i = 0; i < c().size(); i++ ){
		if( n == *c()[i]->node() )
			return c()[i]->dataDouble();
	}
	return INF;
}

void AlgDijkstra::setDistance( const Node &n, double d, const Edge &parent ){
	for( unsigned int i = 0; i < c().size(); i++ ){
		if( n == *c()[i]->node() ){
			c()[i]->setData(d)->setEdge(parent);
			break;
		}
	}
}

Node AlgDijkstra::otherNode( const Edge &e, const Node &n ){
	if( e.from() == n )
		return e.to();
	else
		return e.from();
}
